package binaryTree;

/*
 *@description 从中序与后序遍历序列构造二叉树
 *@author hkfan
 *@version 1.0
 *@create 2025/6/16 15:36
 */
public class LeetCode_106 {
    public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode() {}
        TreeNode(int val) { this.val = val; }
        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }

    public TreeNode buildTree(int[] inorder, int[] postorder) {
        return solution(inorder,postorder,0,inorder.length-1,0,inorder.length-1);
    }

    private TreeNode solution(int[] inorder, int[] postorder, int startA, int endA, int startB, int endB) {
        if (startA<=endA && startB<=endB){
            TreeNode root = new TreeNode(postorder[endB]);
            int i = find(root.val,inorder);
            root.left=solution(inorder,postorder,startA,i-1,startB,startB+i-1-startA);
            root.right=solution(inorder,postorder,i+1,endA,startB+i-startA,endB-1);
            return root;
        }else {
            return null;
        }
    }

    private int find(int val, int[] inorder) {
        for (int i = 0; i < inorder.length; i++) {
            if (val==inorder[i]){
                return i;
            }
        }
        return -1;
    }
}
